package Data_Structure.List.SystemList;

import java.util.Arrays;

/**
 * @className: MyArrayList
 * @author: 芃
 * @description: 模拟源码实现ArrayList
 * @date: 2023/8/24 11:49
 */
public class MyArrayList<E> {
    private Object[] elementData;
    private int usedSize;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int capacity){
        //对参数进行判断
        if (capacity > 0){
            this.elementData = new Object[capacity];
        }else if (capacity == 0){
            this.elementData = new Object[0];
        }else {
            throw new RuntimeException("初始化容量不能为负数");
        }
    }
    //新增元素，默认放在数组的最后位置
    public boolean add(E e){
        //确定一个真正的容量，预测放完元素的个数有多大
        ensureCapacityInternal(usedSize + 1);
        this.elementData[usedSize] = e;
        usedSize++;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        int capacity = calculateCapacity(elementData, minCapacity);
        ensureExplicitCapacity(capacity);
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //是否之前elementData数组分配过大小
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //如果是空数组，则返回10和minCapacity的最大值，即10
            return Math.max(10, minCapacity);
        }
        //分配过 就返回+1后的值
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        //进不去if语句，说明数组还没有放满
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量等于旧容量*1.5
        if (newCapacity - minCapacity < 0){ //如果新容量依然小于minCapacity 则新容量等于minCapacity
            newCapacity = minCapacity;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0){ //如果新容量比上限容量还要大
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?//如果minCapacity大于上限容量，则新容量等于上限容量+8 反之等于上限容量
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    //往指定位置插入元素
    public void add(int index,E e){
        //下标合法性检验
        rangeCheckForAdd(index);
        //确定真实的容量
        ensureCapacityInternal(this.usedSize + 1);
        //元素挪动
        copy(index);
        //新元素插入
        elementData[index] = e;
        //有效数据个数++
        this.usedSize++;
    }
    private void copy(int index){
        for (int i = usedSize - 1; i >= index; i--) {
            elementData[i+1] = elementData[i];
        }
    }
    private void rangeCheckForAdd(int index){
        if (index < 0 || index > size()){
            throw new RuntimeException("下标不合法");
        }
    }

    //获取顺序表的大小
    public int size(){
        return this.usedSize;
    }

    //获取指定下标元素
    public E get(int index){
        if (index < 0 || index >= usedSize){
            throw new ArrayIndexOutOfBoundsException("顺序表下表不合法");
        }else {
            return (E) this.elementData[index];
        }
    }

    //返回第一个e的元素下表
    public int indexOf(Object o){
        if (o == null){
            for (int i = 0; i < usedSize; i++) {
                if (this.elementData[i] == null){
                    return i;
                }
            }
        }else {
            for (int i = 0; i < usedSize; i++) {
                if (o.equals(this.elementData[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    //返回最后一个e的元素下表
    public int lastIndexOf(Object o){
        if (o == null){
            for (int i = usedSize -1; i >= 0; i--) {
                if (this.elementData[i] == null){
                    return i;
                }
            }
        }else {
            for (int i = usedSize - 1; i >= 0; i--) {
                if (o.equals(this.elementData[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    //判断元素e是否存在
    public boolean contains(E e){
        if (e == null){
            for (int i = 0; i < size(); i++) {
                if (this.elementData[i] == null){
                    return true;
                }
            }
        }else {
            for (int i = 0; i < size(); i++) {
                if (e.equals(this.elementData[i])){
                    return true;
                }
            }
        }
        return false;
    }

    //修改指定下表元素
    public void set(int index,E e){
        if (index < 0 || index > this.usedSize){
            throw new RuntimeException("下标不合法");
        }else {
            this.elementData[index] = e;
        }
    }

    //删除index位置的元素
    public void remove(int index){
        if (index < 0 || index > this.usedSize){
            throw new RuntimeException("下标不合法");
        }else {
            copyForRemove(index);
            this.elementData[usedSize-1] = null;
            usedSize--;
        }
    }
    private void copyForRemove(int index){
        for (int i = index; i < this.usedSize; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
    }

    //删除遇到的第一个e
    public boolean remove(E e){
        if (e == null){
            for (int i = 0; i < this.usedSize; i++) {
                if (this.elementData[i] == null){
                    copyForRemove(i);
                }
            }
            this.elementData[usedSize-1] = null;
            usedSize--;
            return true;
        }else {
            for (int i = 0; i < this.usedSize; i++) {
                if (e.equals(this.elementData[i])){
                    copyForRemove(i);
                }
            }
            this.elementData[usedSize-1] = null;
            usedSize--;
            return true;
        }
    }
}
